package Hot100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-12-25 13:51
 */
public class minWindow76 {
    /**76. 最小覆盖子串
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * 滑动窗口：t中字符个数为need
     * */
    public String minWindow(String s, String t) {
        if (s.length()<t.length()) return "";
        HashMap<Character,Integer> window=new HashMap<>(),need=new HashMap<>();
        for (char c:t.toCharArray()) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int count=0;
        int left=0,right=0;
        int reslen=Integer.MAX_VALUE;
        int start=-1;
        while (right<s.length()){
            char c=s.charAt(right);
            right++;
            //将窗口内数据进行一系列更新
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (window.get(c).equals(need.get(c))){//必须用equals，超出常量池后比较会有不同结果
                    count++;
                }
            }
            //左窗口需要收缩
            while (count==need.size()&&left<right){
                //更新结果
                if (right-left<reslen){
                    reslen=right-left;
                    start=left;
                }

                char d=s.charAt(left);
                //窗口更新
                if (need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){
                        //不能判断小于，判断小于会多次减少count
                        count--;
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }
                left++;
            }
        }
        return start==-1?"":s.substring(start,start+reslen);
    }


    /**567. 字符串的排列
     * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
     * 要求为字串，所以找出的长度应该相等
     * */
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length()>s2.length()) return false;
        HashMap<Character,Integer> window=new HashMap<>(),need=new HashMap<>();
        for (char c:s1.toCharArray()) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left=0,right=0,count=0;
        while (right<s2.length()){
            char c=s2.charAt(right);
            right++;
            //更新窗口内数据
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (need.get(c).equals(window.get(c))){
                    count++;
                }
            }
            //缩小左窗口
            while (right-left>=s1.length()){
                if (count==need.size()){
                    return true;
                }
                char d=s2.charAt(left);
                left++;
                if (need.containsKey(d)){
                    if (need.get(d).equals(window.getOrDefault(d,0))){
                        count--;
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }
            }
        }
        return false;
    }

    /**438. 找到字符串中所有字母异位词
     * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
     * */
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length()<p.length()) return new ArrayList<>();
        HashMap<Character,Integer> need=new HashMap<>(),window=new HashMap<>();
        for (char c:p.toCharArray()) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left=0,right=0;
        int count=0;
        List<Integer> res=new ArrayList<>();
        while (right<s.length()){
            char c=s.charAt(right);
            right++;
            //更新窗口内数据
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (window.get(c).equals(need.get(c))){
                    count++;
                }
            }
            //缩小左窗口
            while (right-left>=p.length()&&left<right){
                if (count==need.size()&&right-left==p.length()){
                    res.add(left);
                }
                char d=s.charAt(left);
                left++;
                if (need.containsKey(d)){
                    if (need.get(d).equals(window.get(d))){
                        count--;
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }
            }
        }
        return res;
    }

    /**3. 无重复字符的最长子串
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     * */
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> windows=new HashMap<>();
        int left=0,right=0;
        int res=0;
        while (right<s.length()){
            char c=s.charAt(right);
            right++;
            //更新窗口内的数据
            windows.put(c,windows.getOrDefault(c,0)+1);
            //缩小左窗口
            while (windows.get(c) > 1) {
                char d=s.charAt(left);
                windows.put(d,windows.getOrDefault(d,0)-1);
                left++;
            }
            res=Math.max(res,right-left);
        }
        return res;
    }




    //滑动窗口框架
    void slidingWindow(String s, String t) {
        //在s中找到包含t中所有元素的字串
        HashMap<Character,Integer> window=new HashMap<>();
        HashMap<Character,Integer> need=new HashMap<>();
        for (char c:t.toCharArray()) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left=0,right=0;
        //valid记录有多少字符是符合need要求的
        int valid=0;
        while (right<s.length()){
            // c 是将移入窗口的字符
            char c=s.charAt(right);
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新

            /*** debug 输出的位置 ***/
            System.out.println("window: ["+left+","+right+"]");

            // 判断左侧窗口是否要收缩
            while (window.get(c)>need.get(c)){
                // d 是将移出窗口的字符
                char d=s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新

            }
        }
    }

}
